package com.zto.sch.advance.algorithms;

import java.util.Arrays;

/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-01-17 09:32
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 33, 6, 2, 1, -33, 88, 56};
        printArr(arr);
//        Arrays.sort(arr);
        quickSort(arr, 0, arr.length - 1);
        printArr(arr);
    }

    /**
     * 1，找一个基准值。
     * 2，end向前 <基准值  end--
     * 3,start身后，>基准值 start++
     * 4,
     *5,33,6,2,1,-33,88,56,
     * -33,1,2,5,6,33,88,56,
     */
    private static void quickSort(int[] array, int low, int height) {
        int baseNum = array[0], start = low, end = height;
        //如果指针生命，返回
        if (low == height) {
            return;
        }

        int num = 0;
        while (start < end) {
            num++;
            //从后往前比较：因为start和end值在时刻变化，所以条件要加上：start < end
            while (array[end] >= baseNum && start < end) {
                //如果没有比基准小的，比较下一个
                end--;
            }
            //从前往后比较
            while (array[start] <= baseNum && start < end) {
                //如果大于基准值，交换位置，再比较左边的数据
                start++;
            }
            if (start < end) {
                //如果start<end，交换位置
            }
            swapEach(array, start, end);
            System.out.println("第[" + num + "]次交换后:" + Arrays.toString(array));
        }
        //循环过后，start==end,为基准值位置.low（基准值）与start(或end)互换位置
        swapEach(array, low, start);
        System.out.println("定位后" + Arrays.toString(array));


        //此时第一次循环比较结束，基准值的位置已经确定了。
        // 左边的值都比基准值小，右边的值都比基准值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用

        //如果，start>low,说明前指针有往后移动
        if (start > low) {
            quickSort(array, low, start - 1);
        }
        //如果，end<height，说明后指针有往前移动
        if (end < height) {
            quickSort(array, start + 1, height);
        }


    }

    private static void printArr(int[] arr) {
        for (int a : arr) {
            System.out.print(a + ",");
        }
        System.out.println("");
    }

    private static void swapEach(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
